﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm.Base
{
    /// <summary>
    /// 강한연결성분찾기 알고리즘
    /// </summary>
    class StronglyConnectedComponent
    {
        private List<Edge>[] G; //그래프
        private List<Edge>[] rG; //리버스 그래프
        private List<int> vs; //돌아나오는 순서 나열
        bool[] used;
        int[] cmp; //속하는 강한 연결 성분의 위상적인 순서
        private int maxSize;
        private int V;
        public StronglyConnectedComponent(int maxSize)
        {
            this.maxSize = maxSize;
            V = maxSize;
            G = new List<Edge>[maxSize + 1];
            rG = new List<Edge>[maxSize + 1];
            for (int i = 0; i <= maxSize; i++)
            {
                G[i] = new List<Edge>();
                rG[i] = new List<Edge>();
            }
            vs = new List<int>();
            cmp = new int[maxSize + 1];
            
        }
        public void AddEdge(int from, int to)
        {
            G[from].Add(new Edge(0, to, 0, 0, 0));
            rG[to].Add(new Edge(0, from, 0, 0, 0));
        }
        private void Dfs(int v)
        {
            used[v] = true;
            for (int i = 0; i < G[v].Count; i++)
            {
                if (!used[G[v][i].To]) Dfs(G[v][i].To);
            }
            vs.Add(v);
        }
        private void Rdfs(int v, int k)
        {
            used[v] = true;
            cmp[v] = k;
            for (int i = 0; i < rG[v].Count; i++)
            {
                if(!used[rG[v][i].To]) Rdfs(rG[v][i].To, k);
            }
        }
        public int Scc()
        {
            used = new bool[maxSize + 1];
            vs.Clear();
            for (int v = 0; v < V; v++)
            {
                if (!used[v]) Dfs(v);
            }
            used = new bool[maxSize + 1];
            int k = 0;
            for (int i = vs.Count - 1; i >= 0; i--)
            {
                if (!used[vs[i]]) Rdfs(vs[i], k++);
            }
            return k;
        }
    }
}
